Disk drives interface to a host computer over a host bus. The host computer transmits commands, also known as requests, to read or write data to the disk drive on the host bus. Some host bus interfaces may be characterized as "intelligent" meaning that the device receiving the commands is able to queue commands for optimal execution efficiency. One such bus interface is the Small Computer System Interface, or SCSI bus interface. Conventionally data on a SCSI disk drive is addressed by the host using discrete sequential logical blocks rather than by physical addressing such as head/cylinder/sectors. Read and write commands arrive from the host computer specifying a starting logical block address, also known as a starting LBA, and an LBA range or number of blocks to be transferred. The disk drive then translates an LBA into a physical location on a disk in the disk drive. Conventionally logical blocks are written sequentially on the disk.
A disk drive may be processing a current command when the host sends additional commands. The disk drive may order the commands by arrival time in a queue. The disk drive must then decide what command to execute next. The process of deciding what command to execute next is often handled by a command manager program running in the disk drive. The command manager program determines the order of execution of commands. The order of execution of the commands has an impact on the performance of the disk drive. When a command is not executed in order of arrival time, the command is said to have been "reordered". The process of changing the order of execution of commands is known as "command reordering".
When reordering commands the disk drive may take into account a number of factors including: the age of the command, the mechanical time delay involved in executing the command, and a host time-out period. The host expects the command to have been completed before the host timeout period has expired. The mechanical time delay for a given command may be calculated based on the current location of the read/write head and the location of the data for that command.
Prior art methods of command reordering include real time and non real time methods. Non real time methods do not take into account time constraints of requests. Real time methods take time constraints of requests into account. A review of these types of methods can be found in European Patent Application EP0757310A2 entitled "Controlling Disk Drives". The shortest time first, STF, algorithm considers both seek time and rotational latency but suffers from starvation of commands that are far from the current position. One variant of the shortest time first algorithm, the weighted STF, applies an aging function to the time computed by the shortest time first algorithm. The weighting attempts to solve the starvation problem of the STF algorithm. Other attempts include providing a window of a predetermined number of commands from the oldest command, and if there is enough time to complete more than one command, selecting commands in that window that are in an "elevator" scan to the oldest command. An "elevator" scan heads the arm in the direction of the oldest command and executes commands that are near a scan path to the oldest command.
The highly competitive market for disk drives indicates a continuing need for a better method of selecting commands to achieve higher rates of data transfer without increasing the probability of command timeouts.